题目描述

在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。

输入格式 Input Format

• 只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）

输出格式 Output Format

• 所得的方案数

输入：

3 2

输出：

16

---

想法

状态压缩入门题目，洛谷的题单都这样吗？
感觉写状压的一个好处是只要思路对了，过了样例大概率就能A了(可能是目前做的题太水了)
就是正常的状压思路，hang[i][j][z]表示第i行状态为j已经有了z个国王可行的方案数，然后每一步递推时把上一行可以和谐共存的状态都加上即可。
思路没啥好说的，代码也加上了注释应该能看懂。
不过中间由于没有考虑状态压缩需要枚举的状态其实是0~maxn-1的，结果稍微多调了一会儿，需要记住。以及把行间判错封装成函数确实更方便了。以后或许可以考虑自己实现一些基础结构的封装作为模板

#include<bits/stdc++.h>
using namespace std;
long long n,k,d[20],Kingnum[10010],hang[15][610][101],maxn=1,sum=0;
inline bool panduanhanghefa(int zhuangtai)//判断这一行行内状态是否合法
{
    bool flag=true;
    for(int i=1;i<=n;i++)
        if(zhuangtai&d[i])
            if((zhuangtai&d[i+1])||(zhuangtai&d[i-1])){flag=false;break;}
    return flag;
}
inline bool panduanliehefa(int zhuangtai1,int zhuangtai2)//判断这一行和上一行是否同时合法
{
    bool flag=true;
    for(int i=1;i<=n;i++)
        if(zhuangtai1&d[i])
            if((zhuangtai2&d[i])||(zhuangtai2&d[i+1])||(zhuangtai2&d[i-1])){flag=false;break;}
    return flag;
}int aa[90];
inline void zhuangtaishuchu(int zhuangtai)//输出状态，打表用的
{
    cout<<zhuangtai<<"&&";
    for(int i=zhuangtai;i;i/=2)aa[++aa[0]]=i%2;
    for(int i=aa[0];i>=1;i--)cout<<aa[i];cout<<endl;
    aa[0]=0;
}
int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    cin>>n>>k;
    for(int i=1;i<=n;i++)maxn*=2;//确定状态范围
    d[1]=1;for(int i=2;i<=n;i++)d[i]=d[i-1]<<1;//预处理出判断每一位是否为一的辅助数组
    for(int i=0;i<maxn;i++)for(int j=i;j;j/=2)Kingnum[i]+=j%2;//预处理出状态i所包含的国王数
    for(int i=0;i<maxn;i++)//预处理出第一行的情况
    {
        if(!panduanhanghefa(i))continue;
        hang[1][i][Kingnum[i]]=1;
    }
    for(int i=2;i<=n;i++)//枚举行
    {
        for(int j=0;j<maxn;j++)//枚举当前行状态
        {
            if(!panduanhanghefa(j))continue;//合理剪枝
            for(int j1=0;j1<maxn;j1++)//枚举上一行状态
            {
                if(!panduanhanghefa(j1))continue;//合理剪枝
                if(!panduanliehefa(j,j1))continue;//合理剪枝
                for(int z=0;z<=k;z++)//枚举含有多少个国王
                {
                    if(z<Kingnum[j])continue;//合理剪枝
                    hang[i][j][z]+=hang[i-1][j1][z-Kingnum[j]];
                }
            }
        }
    }
    for(int j=0;j<maxn;j++)sum+=hang[n][j][k];//所有第n行的状态只要满足国王数为k就加到答案上。
    cout<<sum<<endl;
    return 0;
}